//https://leetcode.cn/problems/partition-list-lcci/

struct ListNode* partition(struct ListNode* head, int x) {

    struct ListNode* gGuard, * gTail, * lGuard, * lTail;
    gGuard = gTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    lGuard = lTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    gTail->next = NULL;
    lTail->next = NULL;

    struct ListNode* cur = head;

    while (cur)
    {
        if (cur->val < x)
        {
            lTail->next = cur;
            lTail = lTail->next;
        }
        else
        {
            gTail->next = cur;
            gTail = gTail->next;
        }

        cur = cur->next;
    }

    lTail->next = gGuard->next;
    head = lGuard->next;
    gTail->next = NULL;

    free(gGuard);
    free(lGuard);

    return head;
}
